package com.datastructures.tree;


/**
 * @author MaoLin Wang
 * @date 2019/11/517:51
 */
public class BinaryTreeDemo {
    public static void main(String[] args) {

        BinaryTree binaryTree=new BinaryTree();

        //创建根节点
        TreeNode2 root = new TreeNode2(11);
        TreeNode2 treeNode2 = new TreeNode2(21);
        TreeNode2 treeNode3 = new TreeNode2(31);
        TreeNode2 treeNode4 = new TreeNode2(14);
        TreeNode2 treeNode5 = new TreeNode2(15);
        TreeNode2 treeNode6 = new TreeNode2(61);
        TreeNode2 treeNode7 = new TreeNode2(71);
        TreeNode2 treeNode8 = new TreeNode2(81);
        TreeNode2 treeNode9 = new TreeNode2(91);

        root.lchild =treeNode2;
        root.rchild =treeNode3;
        treeNode3.rchild =treeNode7;
        treeNode3.lchild =treeNode6;
        treeNode2.lchild =treeNode4;
        treeNode2.rchild =treeNode5;
        treeNode4.lchild =treeNode8;
        treeNode4.rchild =treeNode9;
        binaryTree.setRoot(root);
       /* System.out.println("中序-------");

        binaryTree.midOrder();
        System.out.println("前序--------");

        binaryTree.preOrder();
        System.out.println("后续--------");

        binaryTree.postOrder();

        binaryTree.deleteNode(3);
        System.out.println("删除后");
        binaryTree.postOrder();*/
        //前序遍历查找
        System.out.println("前序遍历查找==============");//4次
        TreeNode2 treeNode = binaryTree.preOrderFind(61);
        if (treeNode!=null){
            System.out.println("找到了：编号为"+treeNode.no);
        }else {
            System.out.println("没找到");
        }

        //中序遍历查找
        System.out.println("中序遍历查找====================");//4次
        TreeNode2 midOrderFind = binaryTree.midOrderFind(61);
        if (midOrderFind!=null){
            System.out.println("找到了：编号为："+midOrderFind.no);
        }else {
            System.out.println("没找到");
        }
        //后序遍历查找
        System.out.println("后序遍历查找=============");//2次
        TreeNode2 postOrderFind = binaryTree.postOrderFind(61);
        if (postOrderFind!=null){
            System.out.println("找到了：编号为"+postOrderFind.no);
        }else {
            System.out.println("没找到");
        }
    }
}

//定义二叉树
class BinaryTree {
    private TreeNode2 root;

    public void setRoot(TreeNode2 root) {
        this.root = root;
    }
    //删除节点
    public void deleteNode(int no){
        if (root!=null){
            if (root.no==no){
                //根节点就是目标节点
                root=null;
                return;
            }else {
                //执行删除
                root.deleteNode(no);
            }
        }else {
            System.out.println("二叉树为空");
        }
    }

    //前序遍历
    public void preOrder(){
        if (this.root!=null){
            this.root.preOrder();
        }else {
            System.out.println("二叉树为空");
        }
    }
    //中序遍历
    public void midOrder(){
        if (this.root!=null){
            this.root.midOrder();
        }else {
            System.out.println("二叉树为空");
        }
    }
    //后续遍历
    public void postOrder(){
        if (this.root!=null){
            this.root.postOrder();
        }else {
            System.out.println("二叉树为空");
        }
    }

    /**
     * 前序遍历查找
     * @param no
     * @return
     */
    public TreeNode2 preOrderFind(int no){
        if (root!=null){
            return root.preOrderFind(no);
        }else {
            return null;
        }
    }
    /**
     * 中序遍历查找
     * @param no
     * @return
     */
    public TreeNode2 midOrderFind(int no){
        if (root!=null){
            return root.midOrderFind(no);
        }else {
            return null;

        }
    }
    /**
     * 后序遍历查找
     * @param no
     * @return
     */
    public TreeNode2 postOrderFind(int no){
        if (root!=null){
            return root.postOrderFind(no);
        }else {
            return null;
        }
    }
}

class TreeNode2 {
    public int no;
    public TreeNode2 lchild;
    public TreeNode2 rchild;

    public TreeNode2() {
    }

    public TreeNode2(int no) {
        this.no = no;
    }

    @Override
    public String toString() {
        return "TreeNode2{" +
                "no=" + no +
                '}';
    }



    /**
     * 递归删除
     */
    public void deleteNode(int no){
        if (this.lchild !=null && this.lchild.no==no){
            this.lchild =null;
            return;
        }
        if (this.rchild !=null &&this.rchild.no==no){
            this.rchild =null;
            return;
        }
        if (this.lchild !=null){
            this.lchild.deleteNode(no);
        }
        if (this.rchild !=null){
            this.rchild.deleteNode(no);
        }

    }
    /**
     * 前序遍历： 根节点->左节点->右节点
     */
    public void preOrder() {
        System.out.println(this);//先输出父节点
        //向左递归
        if (this.lchild != null) {
            this.lchild.preOrder();
        }
        //向右递归
        if (this.rchild != null) {
            this.rchild.preOrder();
        }
    }

    /**
     * 中序遍历： 左节点->根节点->右节点
     */
    public void midOrder() {
        //向左递归
        if (this.lchild != null) {
            this.lchild.midOrder();
        }
        System.out.println(this);//先输出父节点

        //向右递归
        if (this.rchild != null) {
            this.rchild.midOrder();
        }
    }

    /**
     * 后序遍历： 左节点->右节点->根节点
     */
    public void postOrder() {
        //向左递归
        if (this.lchild != null) {
            this.lchild.postOrder();
        }


        //向右递归
        if (this.rchild != null) {
            this.rchild.postOrder();
        }
        System.out.println(this);//先输出父节点
    }

    /**
     * 前序遍历查找
     * @param no
     * @return
     */
    public TreeNode2 preOrderFind(int no){


        if (this.no==no){
            return this;
        }
        TreeNode2 treeNode=null;
        /**
         * 判断当前当前节点的左孩子是否为空，不为空 -> 递归前序遍历查找，
         * 若找到，就返回
         */
        if (this.lchild !=null){
           treeNode=this.lchild.preOrderFind(no);
        }
        if (treeNode!=null){
            return treeNode;
        }
        /**
         * 判断右孩子是否为空，不为空->递归前序遍历，无论找没找到都返回treeNode
         */
        if (this.rchild !=null){
            treeNode=this.rchild.preOrderFind(no);
        }

        return treeNode;

    }

    /**
     * 中序遍历查找
     * @param no
     * @return
     */
    public TreeNode2 midOrderFind(int no){

        TreeNode2 treeNode=null;
        /**
         * 判断当前当前节点的左孩子是否为空，不为空 -> 递归前序遍历查找，
         * 若找到，就返回
         */
        if (this.lchild !=null){
            treeNode=this.lchild.midOrderFind(no);
        }
        if (treeNode!=null){
            return treeNode;
        }

        if (this.no==no){
            return this;
        }
        /**
         * 判断右孩子是否为空，不为空->递归前序遍历，无论找没找到都返回treeNode
         */
        if (this.rchild !=null){
            treeNode=this.rchild.midOrderFind(no);
        }

        return treeNode;

    }

    /**
     * 后序遍历查找
     * @param no
     * @return
     */
    public TreeNode2 postOrderFind(int no){

        TreeNode2 treeNode=null;
        /**
         * 判断当前当前节点的左孩子是否为空，不为空 -> 递归前序遍历查找，
         * 若找到，就返回
         */
        if (this.lchild !=null){
            treeNode=this.lchild.postOrderFind(no);
        }
        if (treeNode!=null){
            return treeNode;
        }

        /**
         * 判断右孩子是否为空，不为空->递归前序遍历，无论找没找到都返回treeNode
         */
        if (this.rchild !=null){
            treeNode=this.rchild.postOrderFind(no);
        }

        if (treeNode!=null){
            return treeNode;
        }


        //左右孩子都没找到，找根节点
        if (this.no==no){
            return this;
        }
        return treeNode;

    }
}




